/*
    created: 2023/4/11
    filename: list.c
    author: 李东霖
    purpose： 带头结点的双链表 代码演示
    备注：单链表实现的操作用双链表只会更简单
*/

#include"list.h"

// 初始化链表LL，返回值：失败返回NULL，成功返回头结点的地址。
DNode *InitList1()
{
  DNode *head = (DNode *)malloc(sizeof(DNode));  // 分配头结点。

  if (head == NULL) return NULL;  // 内存不足，返回失败。

  head->prior=head->next=NULL;    // 前驱后继结点都置为空。

  return head;
}

// 传入指针变量的地址的方法。
// 初始化链表，返回值：0-失败；1-成功。
int InitList2(DLinkList *LL)
{
  // 在本函数中，LL是指针的指针，用于存放指针的地址。

  if ( *LL != NULL ) { printf("链表LL已存在，在初始化之前请先释放它。\n"); return 0; }

  DNode *head = (DNode *)malloc(sizeof(DNode));  // 分配头结点。

  if (head == NULL) return 0;  // 内存不足，返回失败。

  head->prior=head->next=NULL;    // 前驱后继结点都置为空。

  *LL=head;

  return 1;
}

/*
// C++引用的方法。
// 初始化链表，返回值：0-失败；1-成功。
int InitList3(DLinkList &LL)
{
  if ( LL != NULL ) { printf("链表L已存在，在初始化之前请先释放它。\n"); return 0; }

  DNode *head = (DNode *)malloc(sizeof(DNode));  // 分配头结点。

  if (head == NULL) return 0;  // 内存不足，返回失败。

  head->prior=head->next=NULL;    // 前驱后继结点都置为空。

  LL=head;

  return 1;
}
*/

// 销毁链表LL。
void DestroyList1(DLinkList LL)
{
  // 销毁链表LL是指释放链表全部的结点，包括头结点。
  DNode *tmp;

  while(LL!=NULL)
  {
    tmp=LL->next;  // tmp保存下一结点的地址。
    free(LL);      // 释放当前结点。
    LL=tmp;        // LL指针移动到下一结点。
  }

  // LL=NULL;   // LL在本函数中相当于局部变量，就算置空了也不会影响调用者传递的LL，所以LL=NULL没有意义。

  return;
}

// 销毁链表LL。
void DestroyList2(DLinkList *LL)
{  
  // 如果函数的参数是指针的指针，可以启用以下代码。
  DNode *tmp1,*tmp2;

  tmp1=*LL;

  while(tmp1!=NULL)
  {
    tmp2=tmp1->next; // tmp保存下一结点的地址。
    free(tmp1);      // 释放当前结点。
    tmp1=tmp2;       // LL指针移动到下一结点。
  }

  *LL=NULL;  // 把链表的指针置为空，表示链表不存在了。

  return;
}

/*
// C++引用的方法。
// 传入指针的地址的方法。
void DestroyList3(DLinkList &LL)
{
  // 销毁链表LL是指释放链表全部的结点，包括头结点。
  DNode *tmp;

  while(LL!=NULL)
  {
    tmp=LL->next;   // tmp保存下一结点的地址。
    free(LL);       // 释放当前结点。
    LL=tmp;         // LL指针移动到下一结点。
  }

  LL=NULL;  // 把链表的指针置为空，表示链表不存在了。

  return;
}
*/

// 清空链表。
void ClearList(DLinkList LL)
{
  // 清空链表LL是指释放链表全部的结点，但不包括头结点。
  if (LL == NULL) { printf("链表LL不存在。\n"); return; } // 判断链表是否存在。

  DNode *tmp1;
  DNode *tmp2=LL->next;  // 保留头结点，从头结点的下一个结点开始释放。

  while(tmp2!=NULL)
  {
    tmp1=tmp2->next;
    free(tmp2);
    tmp2=tmp1;
  }

  LL->next=NULL; // 这行代码一定不能少，否则会留下野指针。

  return;
}

// 在链表LL的第ii个位置插入元素ee，返回值：0-失败；1-成功。
int InsertList(DLinkList LL, unsigned int ii, ElemType *ee)
{
  if ( (LL == NULL) || (ee == NULL) ) { printf("链表LL或元素ee不存在。\n"); return 0; } // 判断表和元素是否存在。

  // 判断插入位置是否合法
  if (ii < 1) { printf("插入位置（%d）不合法，应该在大于0。\n",ii); return 0; }

  // 要在位序ii插入结点，必须找到ii-1结点。
  DNode *pp=LL;  // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。
  int kk=0;      // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。

  while ( (pp != NULL) && (kk < ii-1) )
  {
    pp=pp->next; kk++;

    // printf("pp=%p,kk=%d\n",pp,kk);
  }

  if ( pp==NULL ) { printf("位置（%d）不合法，超过了表长。\n",ii); return 0; }

  DNode *tmp = (DNode *)malloc(sizeof(DNode));  // 分配一个结点。
  if (tmp == NULL) return 0;  // 内存不足，返回失败。
  
  // 考虑数据元素为结构体的情况，这里采用了memcpy的方法而不是直接赋值。
  memcpy(&tmp->data,ee,sizeof(ElemType));

  // 处理前驱后续结点的指针。
  tmp->next=pp->next;
  tmp->prior=pp;
  if (tmp->next != NULL) tmp->next->prior=tmp;  // 特殊处理，如果是在尾部插入，tmp->next根本不存在。
  pp->next=tmp;

  return 1;

  ///////////////////////////////////////
  // 以上代码可以用以下代码代替。
  // DNode *pp=LocateNode(LL,ii-1);  
  // return InsertNextNode(pp,ee);
  ///////////////////////////////////////
}

// 删除链表LL中的第ii个结点，返回值：0-位置ii不合法；1-成功。
int  DeleteNode(DLinkList LL, unsigned int ii)  
{
  if (LL == NULL) { printf("链表L不存在。\n"); return 0; } // 判断链表是否存在。

  // 判断删除位置是否合法
  if (ii < 1) { printf("删除位置（%d）不合法，应该在大于0。\n",ii); return 0; }

  // 要删除位序ii结点，必须找到ii-1结点。
  DNode *pp=LL;  // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。
  int kk=0;      // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。

  while ( (pp != NULL) && (kk < ii-1) )
  {
    pp=pp->next; kk++;
  }

  // 注意，以下行的代码与视频中的不一样，视频中的是 if ( pp==NULL )，有bug。
  if ( pp->next==NULL ) { printf("位置（%d）不合法，超过了表长。\n",ii); return 0; }

  DNode *tmp=pp->next;  // tmp为将要删除的结点。

  // 处理前驱后续结点的指针。
  pp->next=tmp->next;
  if (tmp->next != NULL) tmp->next->prior=pp; // 特殊处理，如果tmp是尾结点，tmp->next根本不存在。

  free(tmp);

  return 1;
}

// 在链表LL的头部插入元素ee，返回值：0-失败；1-成功。
int  PushFront(DLinkList LL, ElemType *ee)
{
  return InsertList(LL,1,ee);
}

// 在链表LL的尾部插入元素ee，返回值：0-失败；1-成功。
int PushBack(DLinkList LL, ElemType *ee)
{
  if ( (LL == NULL) || (ee == NULL) ) { printf("链表LL或元素ee不存在。\n"); return 0; } // 判断表和元素是否存在。

  DNode *pp=LL;  // 从头结点开始。

  // 找到最后一个结点。
  while (pp->next != NULL) pp=pp->next;
  
  DNode *tmp = (DNode *)malloc(sizeof(DNode));  // 分配一个结点。
  if (tmp == NULL) return 0;  // 内存不足，返回失败。
  
  // 考虑数据元素为结构体的情况，这里采用了memcpy的方法而不是直接赋值。
  memcpy(&tmp->data,ee,sizeof(ElemType));

  // 处理前驱后续结点的指针。
  tmp->next=pp->next;
  tmp->prior=pp;
  if (tmp->next != NULL) tmp->next->prior=tmp;  // 特殊处理，如果是在尾部插入，tmp->next根本不存在。
  pp->next=tmp;

  return 1;
}

// 删除链表LL中第一个结点，返回值：0-位置不合法；1-成功。
int PopFront(DLinkList LL)
{
  return DeleteNode(LL, 1);
}

// 删除链表LL中最后一个结点，返回值：0-位置不合法；1-成功。
int PopBack(DLinkList LL)
{
  if ( LL == NULL ) { printf("链表LL不存在。\n"); return 0; } // 判断表和元素是否存在。

  // 必须加上这个判断，不要误删了头结点。
  if ( LL->next == NULL) { printf("链表LL为空，没有尾结点。\n"); return 0; } // 判断表是否为空。

  // 如果是单链表，要删除最后一个结点，必须找到最后一个结点的前一个结点。
  // 如果是双链表，要删除最后一个结点，找到最后一个结点或最后一个结点的前一个结点都可以，但代码实现略有不同。

  DNode *pp=LL;  // 从第0个结点开始。

  // 找到最后一个结点。
  while (pp->next != NULL) pp=pp->next;
 
  pp->prior->next=NULL;  // 把最后一个节点的前一结点的next指针置为空。

  // 释放最后一个结点。
  free(pp);

  return 1;
}

// 打印链表中全部的元素。
void DispList (DLinkList LL)
{
  if (LL == NULL) { printf("链表LL不存在。\n"); return; } // 判断链表是否存在。

  DNode *pp=LL->next;  // 从第1个结点开始。

  while (pp != NULL)
  {
    printf("%-3d", pp->data);  // 如果元素ee为结构体，这行代码要修改。
    pp=pp->next;
  }

  printf("\n");

/*
  // 以下代码用于显示全部结点的地址和元素的值。
  DNode *pp=LL;  // 从第0个结点开始。

  while (pp != NULL)
  {
    printf("pp=%p,prior=%p,next=%p,data=%-3d\n",pp,pp->prior,pp->next,pp->data);  
    pp=pp->next;
  }
*/
}

// 求链表的长度，返回值：>=0-表LL结点的个数。
int  LengthList(DLinkList LL)
{
  if (LL == NULL) { printf("链表LL不存在。\n"); return 0; } // 判断链表是否存在。

  DNode *pp=LL->next;  // 头结点不算，从第1个结点开始。

  int length=0;

  while (pp != NULL) { pp=pp->next; length++; }

  return length;

  // 不使用临时变量，如何计算链表（包括头结点）的长度？
  // if (LL==NULL) return 0;
  // return LengthList(LL->next)+1;
}

// 判断链表是否为空，返回值：0-非空或失败，1-空。
int IsEmpty(DLinkList LL)
{
  if (LL == NULL) return 0;

  if (LL->next == NULL) return 1;

  return 0;
}

// 获取链表中第ii个结点，成功返回结点的地址，失败返回空。
// 注意，ii可以取值为0，表示头结点。
DNode *LocateNode(DLinkList LL, unsigned int ii)
{
  if ( LL == NULL ) { printf("链表LL不存在。\n"); return NULL; } // 判断表和元素是否存在。
  
  DNode *pp=LL;  // 指针pp指向头结点，逐步往后移动，如果为空，表示后面没结点了。
  int kk=0;      // kk指向的是第几个结点，从头结点0开始，pp每向后移动一次，kk就加1。

  while ( (pp != NULL) && (kk < ii) )
  { 
    pp=pp->next; kk++; 
  }

  if ( pp==NULL ) { printf("位置（%d）不合法，超过了表长。\n",ii); return NULL; }

  return pp;
}

// 查找元素ee在链表LL中的结点地址，如果没找到返回NULL，否则返回结点的地址。
DNode *LocateElem(DLinkList LL, ElemType *ee)
{
  DNode *pp=LL->next;  // 从第1个数据结点开始。

  while (pp != NULL)
  {
    // 如果数据元素是结构体，以下代码要修改。
    if (pp->data == *ee) return pp;

    pp = pp->next;
  }

  return NULL;
}

// 在指定结点pp之后插入元素ee，返回值：0-失败；1-成功。
int InsertNextNode(DNode *pp, ElemType *ee)
{
  if (pp == NULL) { printf("结点pp不存在。\n"); return 0; }

  DNode *tmp = (DNode *)malloc(sizeof(DNode));
  if (tmp == NULL) return 0;

  memcpy(&tmp->data,ee,sizeof(ElemType));

  // 处理前驱后续结点的指针。
  tmp->next=pp->next;
  tmp->prior=pp;
  if (tmp->next != NULL) tmp->next->prior=tmp;  // 特殊处理，如果是在尾部插入，tmp->next根本不存在。
  pp->next=tmp;

  return 1;
}

// 在指定结点pp之前插入元素ee，返回值：0-失败；1-成功。
int InsertPriorNode(DNode *pp, ElemType *ee)
{
  if (pp == NULL) { printf("结点pp不存在。\n"); return 0; }

  // 在单链表中，如果要在指定结点pp之前插入元素，采用的是偷梁换柱的方法。
  // 在双链表中，偷不偷都行，因为pp->prior有前驱结点的地址。

  DNode *tmp = (DNode *)malloc(sizeof(DNode));
  if (tmp == NULL) return 0;

  // 把待插入的元素存入tmp中。
  memcpy(&tmp->data,ee,sizeof(ElemType));

  // 处理前驱后继指针。
  tmp->prior=pp->prior;
  pp->prior->next=tmp;

  tmp->next=pp;
  pp->prior=tmp;

  return 1;
}

// 删除指定结点。
int DeleteNode1(DNode *pp)
{
  if (pp == NULL) { printf("结点pp不存在。\n"); return 0; }

  // 在单链表中，删除指定结点根本不可行，也不能采用偷梁换柱的方法。
  // 但是，在双链表中，删除指定结点是可行的。
  
  pp->prior->next=pp->next;
  if (pp->next != NULL) pp->next->prior=pp->prior;  // 特殊处理，如果pp是尾结点，pp->next->prior根本不存在。

  free(pp);

  return 1;
}



/*
//初始化链表，失败返回NULL成功返回链表的头结点，该结点不存放数据
DNode* InitList1()
{
    DDLinkList head = (DDLinkList)malloc(sizeof(DNode));
    head->next = head->prior = NULL;
    return head;
}

//传入指针的地址的初始化方法  
int InitList2(DDLinkList* phead)
{
    *phead = (DDLinkList)malloc(sizeof(DNode));
    (*phead)->next = (*phead)->prior = NULL;
    return 1;
}

//销毁链表
void DestroyList(DDLinkList *phead)
{
    DNode* temp = *phead;
    DNode* del;
    while(temp != NULL)
    {
        del = temp;
        temp = temp->next;
        free(del);
    }
    *phead = NULL;
}

//清空链表  
void ClearList(DDLinkList head)
{
    if(head == NULL) return;
    DNode* temp = head->next;
    DNode* del;
    while(temp != NULL)
    {
        del = temp;
        temp = temp->next;
        free(del);
    }    
    head->next = NULL;
}

//获得链表的长度 返回值 -1-链表为NULL >=0-链表长度 
int LengthList(DDLinkList head)
{
    int length = 0;
    if(head == NULL) return -1;
    DNode* p = head->next;

    while(p != NULL) 
    {
        ++length; 
        p = p->next;
    }
    return length;
}

//在链表的第pos个位置插入元素elem 返回值：0-失败 1-成功 
int InsertList(DDLinkList head,unsigned int pos, ElemType *elem)
{
    if(pos<1) return 0;
    if(head == NULL || elem == NULL) return -1; 

    int loca = 0;
    DNode *p = head;
    while(p != NULL && loca != pos -1)
    {
        ++loca;
        p = p->next;
    }
    if ( p==NULL ) { printf("位置（%d）不合法，超过了表长。\n",pos); return 0; }

    DNode *temp = (DNode*)malloc(sizeof(DNode));
    if(temp == NULL) return 0;
    //考虑到以后会传入结构体
    memcpy(&temp->data,elem,sizeof(ElemType));
    
    temp->next = p->next;
    temp->prior = p;

    if (temp->next != NULL) temp->next->prior=temp;  // 特殊处理，如果是在尾部插入，tmp->next根本不存在。
    p->next=temp;
    
    return 1;

}

//在链表头部插入元素elem  返回值：0-失败 1-成功  
int Push_Front(DDLinkList head,ElemType *elem)
{
    if(head == NULL || elem == NULL) return -1; 
    DNode *p = head;
    DNode *temp = (DNode*)malloc(sizeof(DNode));
    if(temp == NULL) return 0;
    //考虑到以后会传入结构体
    memcpy(&temp->data,elem,sizeof(ElemType));
    temp->next = p->next;
    p->next = temp;

    temp->next->prior = temp;
    temp->prior = p;
    return 1;
    //可以委托给InsertList
}

//在链表尾部插入元素elem  返回值：0-失败 1-成功  
int Push_Back(DDLinkList head,ElemType *elem)
{
    if(head == NULL || elem == NULL) return -1; 
    DNode *p = head;
    while(p->next != NULL) p = p->next;
    DNode *temp = (DNode*)malloc(sizeof(DNode));
    if(temp == NULL) return 0;
    //考虑到以后会传入结构体
    memcpy(&temp->data,elem,sizeof(ElemType));   
    temp->next = p->next;
    p->next = temp;

    temp->next->prior = temp;
    temp->prior = p;
    return 1;
}

//打印链表中的全部元素  
void DispList(DDLinkList head)
{
    DNode* p = head;
    while(p != NULL)
    {
        printf("%d  ",p->data);
        p = p->next;
    }
}

//删除链表中的第pos个结点 返回值0-失败,pos不合法 1-成功
int DeleteNode(DDLinkList head,unsigned int pos)
{
    if(head == NULL) return -1;
    if(pos <1) return 0;
    DNode *p = head;
    int loca = 0;
    while(p != NULL && loca != pos )
    {
        ++loca;
        p = p->next;
    }
    if(p == NULL) return 0;
    p->next->prior = p->prior;
    p->prior->next = p->next;
    free(p);
    return 1;
}

//删除链表的头结点 返回值0-失败,链表是空的 1-成功
int Pop_Front(DDLinkList head)
{
    if(head == NULL) return -1;
    if(head->next == NULL) return 0;
    DNode* p = head->next;
    head->next = p->next;
    free(p);
    return 1;
}

//删除链表的尾结点 返回值0-失败,链表是空的 1-成功
int Pop_Back(DDLinkList head)
{
    if(head == NULL) return -1;
    if(head->next == NULL) return 0;
    DNode *p = head;
    while(p->next != NULL) p = p->next;
    p->prior->next = NULL;
    free(p);
    return 1;
}

//判断链表是否为空 返回值：1-空 0-非空
int Is_Empty(DDLinkList head)
{
    if(head == NULL) return -1;
    if(head->next == NULL) return 1;
    return 0;    
}

//获取链表第pos个结点，成功返回该结点，失败返回NULL
DNode* LocateNode(DDLinkList head,unsigned int pos)
{
    if(head == NULL || head->next == NULL) return NULL;
    if(pos < 1) return NULL;
    int loca = 0;
    DNode* p = head;
    while(p != NULL && loca != pos)
    {
        p = p->next;
        ++loca;
    }
    if(p == NULL) return NULL;
    return p;
}

//查找元素elem在链表中的位置 没有找到该元素返回NULL，否则返回该结点   
DNode* LocateElem(DDLinkList head,ElemType *elem)
{
    if(head == NULL || head->next == NULL || elem == NULL) return NULL;   
    DNode* p = head->next;
    while(p != NULL && p->data != *elem) p = p->next;
    if(p == NULL) return NULL;
    return p;    
}

//在指定结点pp之前插入元素elem 返回值：0-失败 1-成功
int InsertPriorNode(DNode *pp,ElemType *elem)
{
    if( pp == NULL ) return -1;
    if( elem == NULL) return 0;
    DNode* p = (DNode*)malloc(sizeof(DNode));
    if(p == NULL) return 0;
    memcpy(&p->data,elem,sizeof(ElemType));
    p->prior = pp->prior;
    pp->prior->next = p;
    p->next = pp;
    pp->prior = p;
    return 1;
}

//在指定结点pp之后插入元素elem 返回值：0-失败 1-成功
int InsertNextNode(DNode *pp,ElemType *elem)
{
    if( pp == NULL ) return -1;
    if( elem == NULL) return 0;
    DNode* p = (DNode*)malloc(sizeof(DNode));
    if(p == NULL) return 0;
    memcpy(&p->data,elem,sizeof(ElemType));
    p->next = pp->next;
    pp->next->prior = p;
    pp->next = p;
    p->prior = pp;
    return 1;   
}

//删除指定的结点  存在一定的问题  
int DeleteOneNode(DNode *pp)
{   

}

//归并排序，将传入的两个链表合并为一个新链表(升序)  
int MergeList(DDLinkList La,DDLinkList Lb,DDLinkList Lc)
{
    if(La ==NULL ||Lb ==NULL ||Lc ==NULL) return 0;

    DNode* pp;
    La =La->next;
    Lb = Lb->next;
    while(La != NULL && Lb != NULL)
    {
        // 取La和Lb的较小者。
        if (La->data <= Lb->data)
        {
        pp=La; La=La->next;
        }
        else
        {
        pp=Lb; Lb=Lb->next;
        }       
        Lc->next = (DNode*)malloc(sizeof(DNode));
        Lc = Lc->next;
        Lc->next = NULL;
        memcpy(&Lc->data,&pp->data,sizeof(ElemType));
    }
    // 把链表La其它的元素追加到Lc中。
    while (La != NULL)
    {
    Lc->next=(DNode *)malloc(sizeof(DNode));  // 分配一个新结点。
    Lc=Lc->next;
    memcpy(&Lc->data,&La->data,sizeof(ElemType));
    Lc->next=NULL;
    La=La->next;
    }

    // 把链表Lb其它的元素追加到Lc中。
    while (Lb != NULL)
    {
    Lc->next=(DNode *)malloc(sizeof(DNode));  // 分配一个新结点。
    Lc=Lc->next;
    memcpy(&Lc->data,&Lb->data,sizeof(ElemType));
    Lc->next=NULL;
    Lb=Lb->next;
    }

    return 1;       

}

// 把链表pp结点之后的结点原地逆置（反转），返回值：0-失败；1-成功。
void ReverseList(DNode *pp)
{
    DNode *ss;
    DNode *ssnext;

    ss = pp->next;
    pp->next=NULL;  // pp->next指向空。
    while (ss != NULL)
    {
        ssnext=ss->next;  // 保留ss下一结点的地址。
        // 以下三行相当于在pp之后插入ss结点。
        ss->next=pp->next;
        ss->prior = pp;  
        pp->next=ss;
        ss=ssnext;  // ss结点后移。
    }

}
*/